package com.ruijixiang.leetcode.everyday.leetcode2024.leetcode202412;

public class leetcode20241217 {
    /**
     * 三种方法：Z函数/字符串哈希/AC自动机
     * @param words
     * @param target
     * @return
     */
    public int minValidStrings(String[] words,String target){
        int n=target.length();
        int[] maxJumps=new int[n];
        for(String word : words){
            int[] z=calcZ(word+"#"+target);
            int m=word.length()+1;
            for(int i=0;i<n;i++){
                maxJumps[i]=Math.max(maxJumps[i],z[m+i]);
            }
        }
        return jump(maxJumps);
    }

    private int[] calcZ(String S){
        char[] s=S.toCharArray();
        int n=s.length;
        int[] z=new int[n];
        int boxL=0;
        int boxR=0;// z-box左右边界（闭区间）
        for(int i=1;i<n;i++){
            if(i<=boxR){
                z[i]=Math.min(z[i-boxL],boxR-i+1);
            }
            while(i+z[i]<n && s[z[i]]==s[i+z[i]]){
                boxL=i;
                boxR=i+z[i];
                z[i]++;
            }
        }
        return z;
    }

    // 桥的概念
    private int jump(int[] maxJumps){
        int ans=0;
        int curR=0;// 已建造的桥的右端点
        int nxtR=0;// 下一座桥的右端点的最大值
        for(int i=0;i<maxJumps.length;i++){
            nxtR=Math.max(nxtR,i+maxJumps[i]);
            if(i==curR){// 到达已建造的桥的右端点
                if(i==nxtR){// 无论怎么造桥，都无法从i到i+1
                    return -1;
                }
                curR=nxtR;// 造一座桥
                ans++;
            }
        }
        return ans;
    }
}
